直接插入排序
Get the knowledge flowing and circulating! :)
目录
插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到
的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 Insertion Sort 和打扑克牌时,从牌桌上逐一拿起扑克牌,在手上排序的过程相同。
举例:
输入: {3 5 6 7}。
首先拿起第一张牌, 手上有 {5}。
拿起第二张牌 3, 把 3 insert 到手上的牌 {5}, 得到 {3 5}。
拿起第三张牌 7, 把 7 insert 到手上的牌 {3 5}, 得到 {3 5 7}。
拿起第四张牌 6, 把 6 insert 到手上的牌 {3 5 7}, 得到 {3 5 6 7}。
以此类推。
721import java.util.Scanner;
2
3// 这是一个类,名叫Solution
4public class Solution {
5
6 /**
7 * 直接插入排序(Insertion Sort)
8 */
9 public static void main(String[] args) {
10 // TODO Auto-generated method stub
11 System.out.println("Hello, T!");
12
13 Scanner input = new Scanner(System.in);
14
15 int n = input.nextInt();
16
17 int[] arr = new int[n];
18 for (int i = 0; i < n; i++)
19 {
20 arr[i] = input.nextInt();
21 }
22
23 for (int e : arr)
24 {
25 System.out.print(e + " ");
26 }
27 System.out.println("\n--------------");
28
29 Solution sol = new Solution();
30 sol.insertSort_direct(arr, arr.length);
31
32 for (int e : arr)
33 {
34 System.out.print(e + " ");
35 }
36 return;
37 }
38
39 public void insertSort_direct(int[] arr, int n)
40 {
41 for (int i = 0; i < n; i++) {
42 int x = arr[i]; // 取待插入元素【从前到后,依次取】(同时保存这个元素,不怕被覆盖)
43 int j = i - 1; // 依次比较其前面的元素 和 当前这个元素的值
44 while (j >= 0 && x < arr[j]) // 因为j要递减,所以这里要做个条件判断
45 {
46 // 依次移动这个元素
47 arr[j + 1] = arr[j];
48 j--;
49 }
50 // 在空出的位置,放上这个待插入元素
51 arr[j + 1] = x;
52 }
53 }
54
55}
56
57/*
58
59测试样例:
605
615 4 7 9 6
62
639
6465 70 75 80 85 60 55 50 45
65
6610
6710 20 30 40 50 60 70 80 90 100
68
6920
7012 54 63 54 87 52 49 32 65 48 90 27 30 65 3 9 6 14 18 0
71
72 */
(对于数组而言的插入排序)需要比较的次数(Number of comparisons)
边界情况 | 分析过程 | → | 复杂度 |
---|---|---|---|
MIN | (already in order) | → | |
MAX | (in reverse order) | → |
(对于数组而言的插入排序)需要移动的次数(Number of movements)
Same as comparisons!(和比较的次数一样)
※ LaTex基础积累
LaTex 分数:
$\frac{1}{2}$
LaTex 求和(左右):
$\sum_{i=1}^{n-1}i$
LaTex 求和(上下):
$\sum\limits_{i=1}^{n-1}i$